Ćwiczenia/3. Ćwiczenia/Zadanie 1. (Quick Sort maksymalnie O(log n) pamięci).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaimplementować algorytm QuickSort do sortowania n elementowej tablicy tak, żeby zawsze używał najwyżej O(log n) dodatkowej pamięci na stosie, niezależnie od jakości podziałów w funkcji partition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja testująca poprawność algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test_sort(sorting_fn, *, \n",
    "              samples=20,         # A number of tests that will be performed\n",
    "              val_counts=(0, 50), # A minimum and maximum number of values to sort that will be generated\n",
    "              range_=(-100, 100), # A range which will be used to create a random list of values from this range\n",
    "              in_place=True,      # Information whether an algorithm runs in place or not\n",
    "              failed_only=False,  # Show only failed tests. Works only if no_results is set to False\n",
    "              print_out_fn=None,  # An user-defined function to print additional information. Works only if no_results is set to False\n",
    "              no_results=False    # When set to True, no results will be printed (useful only for benchmark)\n",
    "             ):                  \n",
    "    passed = 0                   \n",
    "    for i in range(samples):\n",
    "        random_lst = [random.randint(*range_) for _ in range(random.randint(*val_counts))]\n",
    "        random_lst_before = random_lst[:]\n",
    "        expected = sorted(random_lst)\n",
    "        output = sorting_fn(random_lst)\n",
    "        if not in_place:\n",
    "            random_lst = output\n",
    "        is_correct = random_lst == expected\n",
    "        passed += is_correct\n",
    "        \n",
    "        if not no_results:\n",
    "            if not failed_only or (failed_only and not is_correct):\n",
    "                print(f'TEST #{i+1}:')\n",
    "                print(f'Before sorting: {random_lst_before}')\n",
    "                print(f'After sorting: {random_lst}')\n",
    "                print(f'Expected result: {expected}')\n",
    "                print(f'Test {\"PASSED\" if is_correct else \"FAILED\"}')\n",
    "                print(f'Current passed-to-tested ratio: {passed}/{i+1}')\n",
    "                if print_out_fn:\n",
    "                    print(f'========== Additional results after sorting  ==========')\n",
    "                    print_out_fn(random_lst)\n",
    "                print()\n",
    "                \n",
    "    if not no_results:\n",
    "        print(f'Sorting algorithms is {\"correct\" if passed == samples else \"wrong\"}')\n",
    "        print(f'Passed tests in total: {passed}/{samples}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ nie jest powiedziane, że należy samemu utworzyć stos, uznaję, że należy skorzystać ze stosu systemowego, a więc z rekurencji. Ponieważ również nie można importować dodatkowych bibliotek w tych zadaniach, zdecydowałem się na sztywne ustalenie pivota jako element po lewej stronie przegazanego funkcji partition fragmentu tablicy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(arr):\n",
    "    _quick_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quick_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        pivot_position = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        if pivot_position - left_idx < right_idx - pivot_position:\n",
    "            _quick_sort(arr, left_idx, pivot_position)\n",
    "            left_idx = pivot_position + 1  # I removed a tailing recursion\n",
    "        else:\n",
    "            _quick_sort(arr, pivot_position + 1, right_idx)\n",
    "            right_idx = pivot_position  # I removed a tailing recursion\n",
    "        \n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 2 subarrays of elements lower than or\n",
    "    # equal to a pivot and of elements greater than a pivot (in this\n",
    "    # partition algorithm pivot isn't placed on a fixed position but\n",
    "    # can be also swapped like all the remaining values)\n",
    "    i = left_idx - 1\n",
    "    j = right_idx + 1\n",
    "    while True:\n",
    "        i += 1\n",
    "        while arr[i] < pivot: i += 1\n",
    "            \n",
    "        j -= 1\n",
    "        while arr[j] > pivot: j -= 1\n",
    "        \n",
    "        if i < j:\n",
    "            _swap(arr, i, j)\n",
    "        else:\n",
    "            return j  # Return a pivot position after the last swap\n",
    "\n",
    "    \n",
    "def _swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST #1:\n",
      "Before sorting: [25, 78, -70, -36, 81, 92, -91, 5, -22, 87, 15, -24, -87, 53, 82, -72, 20, 79, -34, 78, -98, 47, 28, 72, -16, -40, -75, -99, 20, -75, -19, -18, 69]\n",
      "After sorting: [-99, -98, -91, -87, -75, -75, -72, -70, -40, -36, -34, -24, -22, -19, -18, -16, 5, 15, 20, 20, 25, 28, 47, 53, 69, 72, 78, 78, 79, 81, 82, 87, 92]\n",
      "Expected result: [-99, -98, -91, -87, -75, -75, -72, -70, -40, -36, -34, -24, -22, -19, -18, -16, 5, 15, 20, 20, 25, 28, 47, 53, 69, 72, 78, 78, 79, 81, 82, 87, 92]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 1/1\n",
      "\n",
      "TEST #2:\n",
      "Before sorting: [-38, 37, -63, 98, -90, -37, -8, 89, 34, 4, -88, 70, 92, -97, 85, 75, -37, 22, -62, 60, -79, 55, 75, 30, 54, 18, -69, -36, 18, 96, -91, 78, 65]\n",
      "After sorting: [-97, -91, -90, -88, -79, -69, -63, -62, -38, -37, -37, -36, -8, 4, 18, 18, 22, 30, 34, 37, 54, 55, 60, 65, 70, 75, 75, 78, 85, 89, 92, 96, 98]\n",
      "Expected result: [-97, -91, -90, -88, -79, -69, -63, -62, -38, -37, -37, -36, -8, 4, 18, 18, 22, 30, 34, 37, 54, 55, 60, 65, 70, 75, 75, 78, 85, 89, 92, 96, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 2/2\n",
      "\n",
      "TEST #3:\n",
      "Before sorting: [45, -21, -19, 50, 7, 45, 0, -15, -16, -40, 18, -91, -62, -85, 82, 6, 57, 61, -34, 12, 62, -62, 5, -93, -45, 39, 91, 28, -97, 6, -88, -19, 75, -53, -80, -98, -69, 71, -64, -59, 12, -92]\n",
      "After sorting: [-98, -97, -93, -92, -91, -88, -85, -80, -69, -64, -62, -62, -59, -53, -45, -40, -34, -21, -19, -19, -16, -15, 0, 5, 6, 6, 7, 12, 12, 18, 28, 39, 45, 45, 50, 57, 61, 62, 71, 75, 82, 91]\n",
      "Expected result: [-98, -97, -93, -92, -91, -88, -85, -80, -69, -64, -62, -62, -59, -53, -45, -40, -34, -21, -19, -19, -16, -15, 0, 5, 6, 6, 7, 12, 12, 18, 28, 39, 45, 45, 50, 57, 61, 62, 71, 75, 82, 91]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 3/3\n",
      "\n",
      "TEST #4:\n",
      "Before sorting: [-22, 17, -60, -58, -84, 76]\n",
      "After sorting: [-84, -60, -58, -22, 17, 76]\n",
      "Expected result: [-84, -60, -58, -22, 17, 76]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 4/4\n",
      "\n",
      "TEST #5:\n",
      "Before sorting: [-11, 16, 26, 14, -99, -97, 76, -85, -60, -43, 65, 73, 21, 79, -33, 57, -71, 57, -14, 14, -94, 99, 21, -42, -23, -67, -27, 97, -72, 11, -57, 31, 65, -92, 11, -19, -72]\n",
      "After sorting: [-99, -97, -94, -92, -85, -72, -72, -71, -67, -60, -57, -43, -42, -33, -27, -23, -19, -14, -11, 11, 11, 14, 14, 16, 21, 21, 26, 31, 57, 57, 65, 65, 73, 76, 79, 97, 99]\n",
      "Expected result: [-99, -97, -94, -92, -85, -72, -72, -71, -67, -60, -57, -43, -42, -33, -27, -23, -19, -14, -11, 11, 11, 14, 14, 16, 21, 21, 26, 31, 57, 57, 65, 65, 73, 76, 79, 97, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 5/5\n",
      "\n",
      "TEST #6:\n",
      "Before sorting: [-65, -4, -84, 62, 38, 38, 0, 16, 46, 18, 87, -58, 7, 98, -65, -79, 4, 45, 30, 70, -76, 58, -88, -38, -7, 99, -100, 72, -4, -26]\n",
      "After sorting: [-100, -88, -84, -79, -76, -65, -65, -58, -38, -26, -7, -4, -4, 0, 4, 7, 16, 18, 30, 38, 38, 45, 46, 58, 62, 70, 72, 87, 98, 99]\n",
      "Expected result: [-100, -88, -84, -79, -76, -65, -65, -58, -38, -26, -7, -4, -4, 0, 4, 7, 16, 18, 30, 38, 38, 45, 46, 58, 62, 70, 72, 87, 98, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 6/6\n",
      "\n",
      "TEST #7:\n",
      "Before sorting: [-58, 79, 37, 68, -84, -89, -99, -48, 85, -5]\n",
      "After sorting: [-99, -89, -84, -58, -48, -5, 37, 68, 79, 85]\n",
      "Expected result: [-99, -89, -84, -58, -48, -5, 37, 68, 79, 85]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 7/7\n",
      "\n",
      "TEST #8:\n",
      "Before sorting: [19, 96, -1, -66, -29, 12, 1, -12, -32, -35, 86, 41, 25, 41, 93, 71, 98, 55, -96, 39, 96, -17, 73, -32, 16, -6, -38, 55, -19, -38, 55, -58, -79, -89, 15, -26, 1, -62]\n",
      "After sorting: [-96, -89, -79, -66, -62, -58, -38, -38, -35, -32, -32, -29, -26, -19, -17, -12, -6, -1, 1, 1, 12, 15, 16, 19, 25, 39, 41, 41, 55, 55, 55, 71, 73, 86, 93, 96, 96, 98]\n",
      "Expected result: [-96, -89, -79, -66, -62, -58, -38, -38, -35, -32, -32, -29, -26, -19, -17, -12, -6, -1, 1, 1, 12, 15, 16, 19, 25, 39, 41, 41, 55, 55, 55, 71, 73, 86, 93, 96, 96, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 8/8\n",
      "\n",
      "TEST #9:\n",
      "Before sorting: [-68, 15, -42, 28, 13, -90, 33, 74, -27, 41, -4, 79, -14, 41, -12, 21, 80, 25, -28, 63]\n",
      "After sorting: [-90, -68, -42, -28, -27, -14, -12, -4, 13, 15, 21, 25, 28, 33, 41, 41, 63, 74, 79, 80]\n",
      "Expected result: [-90, -68, -42, -28, -27, -14, -12, -4, 13, 15, 21, 25, 28, 33, 41, 41, 63, 74, 79, 80]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 9/9\n",
      "\n",
      "TEST #10:\n",
      "Before sorting: [58, -92, -72, -27, -37, -13, -41, -73, 90, -85, 16, 45, 46, 80, 73, -29, -98, 79, 99, -36, 16, 82, -81, -86, 97, 58, -71, -18, -3, 19, -12, 89, -84, 64, -92, 2, 63, 70, -67, -89, -64, 56, 27, -46, -5, 0, 67, 81, -8]\n",
      "After sorting: [-98, -92, -92, -89, -86, -85, -84, -81, -73, -72, -71, -67, -64, -46, -41, -37, -36, -29, -27, -18, -13, -12, -8, -5, -3, 0, 2, 16, 16, 19, 27, 45, 46, 56, 58, 58, 63, 64, 67, 70, 73, 79, 80, 81, 82, 89, 90, 97, 99]\n",
      "Expected result: [-98, -92, -92, -89, -86, -85, -84, -81, -73, -72, -71, -67, -64, -46, -41, -37, -36, -29, -27, -18, -13, -12, -8, -5, -3, 0, 2, 16, 16, 19, 27, 45, 46, 56, 58, 58, 63, 64, 67, 70, 73, 79, 80, 81, 82, 89, 90, 97, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 10/10\n",
      "\n",
      "TEST #11:\n",
      "Before sorting: [-49, -72, 64, -15, -96, 35, -43, 70, 77, -43, -48, -20, -16, 67, 46, -68, 30, -15, 43, 64, -56, -89, 7, -55, -51, -14, 60, -8, -83, 97, -49, 4]\n",
      "After sorting: [-96, -89, -83, -72, -68, -56, -55, -51, -49, -49, -48, -43, -43, -20, -16, -15, -15, -14, -8, 4, 7, 30, 35, 43, 46, 60, 64, 64, 67, 70, 77, 97]\n",
      "Expected result: [-96, -89, -83, -72, -68, -56, -55, -51, -49, -49, -48, -43, -43, -20, -16, -15, -15, -14, -8, 4, 7, 30, 35, 43, 46, 60, 64, 64, 67, 70, 77, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 11/11\n",
      "\n",
      "TEST #12:\n",
      "Before sorting: [-56, -64, 70, 28, 10, -5, -6, -87, 56, 47, -22, 30, 17, -22, 10, -38, 64, -15, -21, -62, -14, -10, -30, 43, -81, -59, -30, -5, -18, -21, 87, 83, 98, -89, -70, 39, 64, 28, 62, -42]\n",
      "After sorting: [-89, -87, -81, -70, -64, -62, -59, -56, -42, -38, -30, -30, -22, -22, -21, -21, -18, -15, -14, -10, -6, -5, -5, 10, 10, 17, 28, 28, 30, 39, 43, 47, 56, 62, 64, 64, 70, 83, 87, 98]\n",
      "Expected result: [-89, -87, -81, -70, -64, -62, -59, -56, -42, -38, -30, -30, -22, -22, -21, -21, -18, -15, -14, -10, -6, -5, -5, 10, 10, 17, 28, 28, 30, 39, 43, 47, 56, 62, 64, 64, 70, 83, 87, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 12/12\n",
      "\n",
      "TEST #13:\n",
      "Before sorting: [-62, -81, 67, -43, -16, -35, -5, -58, 70, -26, -91, -50, -72, 93, -10, -85, 32, 95, -77, -2, -56, -5, -19, 87, 58, 17, 23, 87, 74, -36, 89, -34, -57, -49]\n",
      "After sorting: [-91, -85, -81, -77, -72, -62, -58, -57, -56, -50, -49, -43, -36, -35, -34, -26, -19, -16, -10, -5, -5, -2, 17, 23, 32, 58, 67, 70, 74, 87, 87, 89, 93, 95]\n",
      "Expected result: [-91, -85, -81, -77, -72, -62, -58, -57, -56, -50, -49, -43, -36, -35, -34, -26, -19, -16, -10, -5, -5, -2, 17, 23, 32, 58, 67, 70, 74, 87, 87, 89, 93, 95]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 13/13\n",
      "\n",
      "TEST #14:\n",
      "Before sorting: [5, -17, 73, -97, 88, 88, 70, -58, -73, -63, 50, -72, 86, 96, -65, 3, -4]\n",
      "After sorting: [-97, -73, -72, -65, -63, -58, -17, -4, 3, 5, 50, 70, 73, 86, 88, 88, 96]\n",
      "Expected result: [-97, -73, -72, -65, -63, -58, -17, -4, 3, 5, 50, 70, 73, 86, 88, 88, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 14/14\n",
      "\n",
      "TEST #15:\n",
      "Before sorting: [-14, -66, 12, -92, 21, 66, 33, 70, 90, -57, -91, -81, 50, -7, 49, -62, -21, -83, -83, -100, 28, 17, -89, 5, 85, 22, 1, 28, 59, -45, 36, -1, -21, 8, -91, -4, -62, 37]\n",
      "After sorting: [-100, -92, -91, -91, -89, -83, -83, -81, -66, -62, -62, -57, -45, -21, -21, -14, -7, -4, -1, 1, 5, 8, 12, 17, 21, 22, 28, 28, 33, 36, 37, 49, 50, 59, 66, 70, 85, 90]\n",
      "Expected result: [-100, -92, -91, -91, -89, -83, -83, -81, -66, -62, -62, -57, -45, -21, -21, -14, -7, -4, -1, 1, 5, 8, 12, 17, 21, 22, 28, 28, 33, 36, 37, 49, 50, 59, 66, 70, 85, 90]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 15/15\n",
      "\n",
      "TEST #16:\n",
      "Before sorting: [-96, 90, 74, -70, 0, -5, 31, 40, 75]\n",
      "After sorting: [-96, -70, -5, 0, 31, 40, 74, 75, 90]\n",
      "Expected result: [-96, -70, -5, 0, 31, 40, 74, 75, 90]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 16/16\n",
      "\n",
      "TEST #17:\n",
      "Before sorting: [61, 41, -23, -82, -97, -74, -10, -81, -69, 70, -57, -49, 27, 69]\n",
      "After sorting: [-97, -82, -81, -74, -69, -57, -49, -23, -10, 27, 41, 61, 69, 70]\n",
      "Expected result: [-97, -82, -81, -74, -69, -57, -49, -23, -10, 27, 41, 61, 69, 70]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 17/17\n",
      "\n",
      "TEST #18:\n",
      "Before sorting: [4, -13, -6, -44, -65, -10, 56, 97, -77, -4, 1, 77, -20, 58, 82, 72, -79, 33, 95, 42, 64, -95, 59, -50, 84, -50, -47, 13, 43, 47]\n",
      "After sorting: [-95, -79, -77, -65, -50, -50, -47, -44, -20, -13, -10, -6, -4, 1, 4, 13, 33, 42, 43, 47, 56, 58, 59, 64, 72, 77, 82, 84, 95, 97]\n",
      "Expected result: [-95, -79, -77, -65, -50, -50, -47, -44, -20, -13, -10, -6, -4, 1, 4, 13, 33, 42, 43, 47, 56, 58, 59, 64, 72, 77, 82, 84, 95, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 18/18\n",
      "\n",
      "TEST #19:\n",
      "Before sorting: [63, -18, -67, -24, 91, 47, 33, -75, 77, -7, 80, -19, -44, 26, -87, -44, 82, -99, -5, -16, -11, 32, -69, 21]\n",
      "After sorting: [-99, -87, -75, -69, -67, -44, -44, -24, -19, -18, -16, -11, -7, -5, 21, 26, 32, 33, 47, 63, 77, 80, 82, 91]\n",
      "Expected result: [-99, -87, -75, -69, -67, -44, -44, -24, -19, -18, -16, -11, -7, -5, 21, 26, 32, 33, 47, 63, 77, 80, 82, 91]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 19/19\n",
      "\n",
      "TEST #20:\n",
      "Before sorting: [68, -33, -46, -58, -77, 67, -4, -99, 57, 56, 85, 75, 77, 56, 6, 53, -51, 44, -3, 15, -24, -76, -2, 10, -86, 86, -43, 94, -51, -47, -78, -86, 81, -49, 86, -7, -51, 42, 80, 4, -61, -44, 55, 38, 17, -31, 75, 63]\n",
      "After sorting: [-99, -86, -86, -78, -77, -76, -61, -58, -51, -51, -51, -49, -47, -46, -44, -43, -33, -31, -24, -7, -4, -3, -2, 4, 6, 10, 15, 17, 38, 42, 44, 53, 55, 56, 56, 57, 63, 67, 68, 75, 75, 77, 80, 81, 85, 86, 86, 94]\n",
      "Expected result: [-99, -86, -86, -78, -77, -76, -61, -58, -51, -51, -51, -49, -47, -46, -44, -43, -33, -31, -24, -7, -4, -3, -2, 4, 6, 10, 15, 17, 38, 42, 44, 53, 55, 56, 56, 57, 63, 67, 68, 75, 75, 77, 80, 81, 85, 86, 86, 94]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 20/20\n",
      "\n",
      "TEST #21:\n",
      "Before sorting: [-72, -67, -89, -68, -49, -38, 93, -83, -49, -4, -60, 84, 64, 96, 64, -39, 65, 54, 41, 17, -51, 0, -48, -37, 33, -43, -44, 79, -44, -24, -78, 65, 66, -84, 58, 82, 59, -10, 59, 70, -20, 45, -74, -30, 65, 80, -38]\n",
      "After sorting: [-89, -84, -83, -78, -74, -72, -68, -67, -60, -51, -49, -49, -48, -44, -44, -43, -39, -38, -38, -37, -30, -24, -20, -10, -4, 0, 17, 33, 41, 45, 54, 58, 59, 59, 64, 64, 65, 65, 65, 66, 70, 79, 80, 82, 84, 93, 96]\n",
      "Expected result: [-89, -84, -83, -78, -74, -72, -68, -67, -60, -51, -49, -49, -48, -44, -44, -43, -39, -38, -38, -37, -30, -24, -20, -10, -4, 0, 17, 33, 41, 45, 54, 58, 59, 59, 64, 64, 65, 65, 65, 66, 70, 79, 80, 82, 84, 93, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 21/21\n",
      "\n",
      "TEST #22:\n",
      "Before sorting: [78, -2, 100, 82, 44, -25, -48, -100, 21, -52, -80]\n",
      "After sorting: [-100, -80, -52, -48, -25, -2, 21, 44, 78, 82, 100]\n",
      "Expected result: [-100, -80, -52, -48, -25, -2, 21, 44, 78, 82, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 22/22\n",
      "\n",
      "TEST #23:\n",
      "Before sorting: [40, 89, 62, -43, -67, -20, 93, 2, -97, -43, -93, 30, -13, -38, 39, -8, 56, 20, 59, 86, -90, 21]\n",
      "After sorting: [-97, -93, -90, -67, -43, -43, -38, -20, -13, -8, 2, 20, 21, 30, 39, 40, 56, 59, 62, 86, 89, 93]\n",
      "Expected result: [-97, -93, -90, -67, -43, -43, -38, -20, -13, -8, 2, 20, 21, 30, 39, 40, 56, 59, 62, 86, 89, 93]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 23/23\n",
      "\n",
      "TEST #24:\n",
      "Before sorting: [81, 66, 80, -49, 79, 31, -68, -52, 9, 43, -59, 95, -30, 50, -70, -61, 43, -47, 76, -28, 98, -40, -69, -16, -41, 62, -56, -40, -1]\n",
      "After sorting: [-70, -69, -68, -61, -59, -56, -52, -49, -47, -41, -40, -40, -30, -28, -16, -1, 9, 31, 43, 43, 50, 62, 66, 76, 79, 80, 81, 95, 98]\n",
      "Expected result: [-70, -69, -68, -61, -59, -56, -52, -49, -47, -41, -40, -40, -30, -28, -16, -1, 9, 31, 43, 43, 50, 62, 66, 76, 79, 80, 81, 95, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 24/24\n",
      "\n",
      "TEST #25:\n",
      "Before sorting: [-56, 21, -57, 42, -60, 44, -87, 42, -62, 55, -31, 23, -47, -32, -31, -23]\n",
      "After sorting: [-87, -62, -60, -57, -56, -47, -32, -31, -31, -23, 21, 23, 42, 42, 44, 55]\n",
      "Expected result: [-87, -62, -60, -57, -56, -47, -32, -31, -31, -23, 21, 23, 42, 42, 44, 55]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 25/25\n",
      "\n",
      "TEST #26:\n",
      "Before sorting: [46, -81, 60, -97, -100, 58, -93, 18, -88, -100, 15, -71, -40, 93, 3, 75]\n",
      "After sorting: [-100, -100, -97, -93, -88, -81, -71, -40, 3, 15, 18, 46, 58, 60, 75, 93]\n",
      "Expected result: [-100, -100, -97, -93, -88, -81, -71, -40, 3, 15, 18, 46, 58, 60, 75, 93]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 26/26\n",
      "\n",
      "TEST #27:\n",
      "Before sorting: [-14, 13, -88, -11, 76, 45, -72, 10, -24, 81, -30, 15, -21, 18, 95, 59]\n",
      "After sorting: [-88, -72, -30, -24, -21, -14, -11, 10, 13, 15, 18, 45, 59, 76, 81, 95]\n",
      "Expected result: [-88, -72, -30, -24, -21, -14, -11, 10, 13, 15, 18, 45, 59, 76, 81, 95]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 27/27\n",
      "\n",
      "TEST #28:\n",
      "Before sorting: [90, -39, -55, 72, 21, -68, 100, 62, -59, -47, -63, 22, 14, -40, 82, 0, 14, -47, -6, -30, -83, 100, 35, -63, 74]\n",
      "After sorting: [-83, -68, -63, -63, -59, -55, -47, -47, -40, -39, -30, -6, 0, 14, 14, 21, 22, 35, 62, 72, 74, 82, 90, 100, 100]\n",
      "Expected result: [-83, -68, -63, -63, -59, -55, -47, -47, -40, -39, -30, -6, 0, 14, 14, 21, 22, 35, 62, 72, 74, 82, 90, 100, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 28/28\n",
      "\n",
      "TEST #29:\n",
      "Before sorting: [19, -15, -92, 58, -42, -8, 13, -39, 63, -82, 100, -12, -54, -8, -81, -73, 43, -87, -16, -48, -5, -48, 78, -83, -68, 67, 31, -25, 38, 84, 9, 66, 93, -81, -52, -64, 45, -15, 37, 46, 38, -86]\n",
      "After sorting: [-92, -87, -86, -83, -82, -81, -81, -73, -68, -64, -54, -52, -48, -48, -42, -39, -25, -16, -15, -15, -12, -8, -8, -5, 9, 13, 19, 31, 37, 38, 38, 43, 45, 46, 58, 63, 66, 67, 78, 84, 93, 100]\n",
      "Expected result: [-92, -87, -86, -83, -82, -81, -81, -73, -68, -64, -54, -52, -48, -48, -42, -39, -25, -16, -15, -15, -12, -8, -8, -5, 9, 13, 19, 31, 37, 38, 38, 43, 45, 46, 58, 63, 66, 67, 78, 84, 93, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 29/29\n",
      "\n",
      "TEST #30:\n",
      "Before sorting: [27, -22, 55, -96, -74, -38, -99, 0, -80, 19, -69, -1, -17, -30, 70, -42, -79, -61, 17, 84, 52, 43, -98, -78, -26, 8]\n",
      "After sorting: [-99, -98, -96, -80, -79, -78, -74, -69, -61, -42, -38, -30, -26, -22, -17, -1, 0, 8, 17, 19, 27, 43, 52, 55, 70, 84]\n",
      "Expected result: [-99, -98, -96, -80, -79, -78, -74, -69, -61, -42, -38, -30, -26, -22, -17, -1, 0, 8, 17, 19, 27, 43, 52, 55, 70, 84]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 30/30\n",
      "\n",
      "TEST #31:\n",
      "Before sorting: [-45, -37, -84]\n",
      "After sorting: [-84, -45, -37]\n",
      "Expected result: [-84, -45, -37]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 31/31\n",
      "\n",
      "TEST #32:\n",
      "Before sorting: [-19, -34, 58, 11, -4, 92, 22, 2, -28, -33, -72, -38, 97, -55, 12, -87, -78, 63, 17, 43, -97, -38, 72, -93, 71, 89, -99, -54, 1, 87, 1, 34, -70, -60, 9, 74, -62, -65, -97, -15, 86, -15, 7, 6, -15, -28, -29, 93]\n",
      "After sorting: [-99, -97, -97, -93, -87, -78, -72, -70, -65, -62, -60, -55, -54, -38, -38, -34, -33, -29, -28, -28, -19, -15, -15, -15, -4, 1, 1, 2, 6, 7, 9, 11, 12, 17, 22, 34, 43, 58, 63, 71, 72, 74, 86, 87, 89, 92, 93, 97]\n",
      "Expected result: [-99, -97, -97, -93, -87, -78, -72, -70, -65, -62, -60, -55, -54, -38, -38, -34, -33, -29, -28, -28, -19, -15, -15, -15, -4, 1, 1, 2, 6, 7, 9, 11, 12, 17, 22, 34, 43, 58, 63, 71, 72, 74, 86, 87, 89, 92, 93, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 32/32\n",
      "\n",
      "TEST #33:\n",
      "Before sorting: [66, -93, 72, -17, 23, -56, 31, 70, -60, 9, -12, 55, -19, -3, -100, -5, -14, 85, 3, 59, 46, -10, 43, 86, 26, 95, 89, -79]\n",
      "After sorting: [-100, -93, -79, -60, -56, -19, -17, -14, -12, -10, -5, -3, 3, 9, 23, 26, 31, 43, 46, 55, 59, 66, 70, 72, 85, 86, 89, 95]\n",
      "Expected result: [-100, -93, -79, -60, -56, -19, -17, -14, -12, -10, -5, -3, 3, 9, 23, 26, 31, 43, 46, 55, 59, 66, 70, 72, 85, 86, 89, 95]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 33/33\n",
      "\n",
      "TEST #34:\n",
      "Before sorting: [-65, -99, 69, 64, 77, 42, -32, 27, -22, 45, -17, 100, -33, -10, 100]\n",
      "After sorting: [-99, -65, -33, -32, -22, -17, -10, 27, 42, 45, 64, 69, 77, 100, 100]\n",
      "Expected result: [-99, -65, -33, -32, -22, -17, -10, 27, 42, 45, 64, 69, 77, 100, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 34/34\n",
      "\n",
      "TEST #35:\n",
      "Before sorting: [93, -91, -59, 14, 29, -8, 27, 51, 30, -52, 78, 73, -61, 19, -57, 28, 30, -52, 71, -42, -43, 14, -18, 75, 96, -28, 25, -46, -92, -59, -55, -97, -90, -75, -51, -53, 61, 19, 48, -83, 32, 16, -60]\n",
      "After sorting: [-97, -92, -91, -90, -83, -75, -61, -60, -59, -59, -57, -55, -53, -52, -52, -51, -46, -43, -42, -28, -18, -8, 14, 14, 16, 19, 19, 25, 27, 28, 29, 30, 30, 32, 48, 51, 61, 71, 73, 75, 78, 93, 96]\n",
      "Expected result: [-97, -92, -91, -90, -83, -75, -61, -60, -59, -59, -57, -55, -53, -52, -52, -51, -46, -43, -42, -28, -18, -8, 14, 14, 16, 19, 19, 25, 27, 28, 29, 30, 30, 32, 48, 51, 61, 71, 73, 75, 78, 93, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 35/35\n",
      "\n",
      "TEST #36:\n",
      "Before sorting: [68, -83, 85, 100, 6, -12, -5, 64, -86, -83, -32, 91, -58, 99, -81, -75, -80, 96, -41, 16, 98, -49, -23, 18, -85, -34, 48, -76, 47, -63, -43, 59, 52, -79, -42, -12, 54]\n",
      "After sorting: [-86, -85, -83, -83, -81, -80, -79, -76, -75, -63, -58, -49, -43, -42, -41, -34, -32, -23, -12, -12, -5, 6, 16, 18, 47, 48, 52, 54, 59, 64, 68, 85, 91, 96, 98, 99, 100]\n",
      "Expected result: [-86, -85, -83, -83, -81, -80, -79, -76, -75, -63, -58, -49, -43, -42, -41, -34, -32, -23, -12, -12, -5, 6, 16, 18, 47, 48, 52, 54, 59, 64, 68, 85, 91, 96, 98, 99, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 36/36\n",
      "\n",
      "TEST #37:\n",
      "Before sorting: [-41, 92, -38, 10, -79, 63, 0, -75, 69, -89, 70, -56, -72, -15, 56, -52, 54, -43, -51, 60]\n",
      "After sorting: [-89, -79, -75, -72, -56, -52, -51, -43, -41, -38, -15, 0, 10, 54, 56, 60, 63, 69, 70, 92]\n",
      "Expected result: [-89, -79, -75, -72, -56, -52, -51, -43, -41, -38, -15, 0, 10, 54, 56, 60, 63, 69, 70, 92]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 37/37\n",
      "\n",
      "TEST #38:\n",
      "Before sorting: [53, 81, -86, -68, -59, 47, 53, -9, -92, -81, 29, -80, -33, -26, 76, -9, 12, -89, -22, 68, 35, 53, 8, 55, 27, 54, -64]\n",
      "After sorting: [-92, -89, -86, -81, -80, -68, -64, -59, -33, -26, -22, -9, -9, 8, 12, 27, 29, 35, 47, 53, 53, 53, 54, 55, 68, 76, 81]\n",
      "Expected result: [-92, -89, -86, -81, -80, -68, -64, -59, -33, -26, -22, -9, -9, 8, 12, 27, 29, 35, 47, 53, 53, 53, 54, 55, 68, 76, 81]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 38/38\n",
      "\n",
      "TEST #39:\n",
      "Before sorting: [-5, -69, -32, -76, -3, 35, -32, 71, 71, 83, 15, 66, 20, 99, 53, -72, -60, -14, 55, -82, -36, 66, -78, 89, -85, -32, 100, -24, -12, 66, 81, -86, -17, 43, 71, 82, 55, 33, -35, -60]\n",
      "After sorting: [-86, -85, -82, -78, -76, -72, -69, -60, -60, -36, -35, -32, -32, -32, -24, -17, -14, -12, -5, -3, 15, 20, 33, 35, 43, 53, 55, 55, 66, 66, 66, 71, 71, 71, 81, 82, 83, 89, 99, 100]\n",
      "Expected result: [-86, -85, -82, -78, -76, -72, -69, -60, -60, -36, -35, -32, -32, -32, -24, -17, -14, -12, -5, -3, 15, 20, 33, 35, 43, 53, 55, 55, 66, 66, 66, 71, 71, 71, 81, 82, 83, 89, 99, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 39/39\n",
      "\n",
      "TEST #40:\n",
      "Before sorting: [37, -16, 26, 42, 78, 94, 42, -27, 61, 19, 82, 75, 51, -62, 38, 16, -97, -98, -100, 42, 37, 81, 14, -67, -100, 39, -40, 75, -83, -69, 82, 98, -70, -32, -24, -45, 49, 20, 74, 72, 68]\n",
      "After sorting: [-100, -100, -98, -97, -83, -70, -69, -67, -62, -45, -40, -32, -27, -24, -16, 14, 16, 19, 20, 26, 37, 37, 38, 39, 42, 42, 42, 49, 51, 61, 68, 72, 74, 75, 75, 78, 81, 82, 82, 94, 98]\n",
      "Expected result: [-100, -100, -98, -97, -83, -70, -69, -67, -62, -45, -40, -32, -27, -24, -16, 14, 16, 19, 20, 26, 37, 37, 38, 39, 42, 42, 42, 49, 51, 61, 68, 72, 74, 75, 75, 78, 81, 82, 82, 94, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 40/40\n",
      "\n",
      "TEST #41:\n",
      "Before sorting: [90, 8, -78, 4, -29, -42, -91, -77, -27, 91, 59, -81, 76, -68, 6, -57, 84, -42, -78, 35, 35, -42, 42, -68, -54, -44, -58, 60, -88, 30, -39, -91, 49, 63, 35, -58, 23, 77, 23, 54, 92, -46, -30, 66, -86, 31]\n",
      "After sorting: [-91, -91, -88, -86, -81, -78, -78, -77, -68, -68, -58, -58, -57, -54, -46, -44, -42, -42, -42, -39, -30, -29, -27, 4, 6, 8, 23, 23, 30, 31, 35, 35, 35, 42, 49, 54, 59, 60, 63, 66, 76, 77, 84, 90, 91, 92]\n",
      "Expected result: [-91, -91, -88, -86, -81, -78, -78, -77, -68, -68, -58, -58, -57, -54, -46, -44, -42, -42, -42, -39, -30, -29, -27, 4, 6, 8, 23, 23, 30, 31, 35, 35, 35, 42, 49, 54, 59, 60, 63, 66, 76, 77, 84, 90, 91, 92]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 41/41\n",
      "\n",
      "TEST #42:\n",
      "Before sorting: [-69, 56, -23, 96, -100, 95, 13, 93, -61, 82, -66, -78, -44, -64, 48, -30, 79, -85, 76, -48, -24, -49, -63, 11, -71, -52, 74, -35, -53, 66, -61, -91, -92, -18, -64, 54, 54, 10, -10, 51, -24, 67, -31, -5, -21, 27]\n",
      "After sorting: [-100, -92, -91, -85, -78, -71, -69, -66, -64, -64, -63, -61, -61, -53, -52, -49, -48, -44, -35, -31, -30, -24, -24, -23, -21, -18, -10, -5, 10, 11, 13, 27, 48, 51, 54, 54, 56, 66, 67, 74, 76, 79, 82, 93, 95, 96]\n",
      "Expected result: [-100, -92, -91, -85, -78, -71, -69, -66, -64, -64, -63, -61, -61, -53, -52, -49, -48, -44, -35, -31, -30, -24, -24, -23, -21, -18, -10, -5, 10, 11, 13, 27, 48, 51, 54, 54, 56, 66, 67, 74, 76, 79, 82, 93, 95, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 42/42\n",
      "\n",
      "TEST #43:\n",
      "Before sorting: [55, 67, 22, 38, -36, -18, 14, -38, 61, 31, 96, -93, -90, 62, 95, 85, 13, 95, 32, -3, 22, -39, 7, 0, 37]\n",
      "After sorting: [-93, -90, -39, -38, -36, -18, -3, 0, 7, 13, 14, 22, 22, 31, 32, 37, 38, 55, 61, 62, 67, 85, 95, 95, 96]\n",
      "Expected result: [-93, -90, -39, -38, -36, -18, -3, 0, 7, 13, 14, 22, 22, 31, 32, 37, 38, 55, 61, 62, 67, 85, 95, 95, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 43/43\n",
      "\n",
      "TEST #44:\n",
      "Before sorting: [8, 30, -4, 36, 77, -15, -51, -39, -46, -85, -67, -90, 84, -55, 31, 1, -63, -38, -79, -18, 53, -3]\n",
      "After sorting: [-90, -85, -79, -67, -63, -55, -51, -46, -39, -38, -18, -15, -4, -3, 1, 8, 30, 31, 36, 53, 77, 84]\n",
      "Expected result: [-90, -85, -79, -67, -63, -55, -51, -46, -39, -38, -18, -15, -4, -3, 1, 8, 30, 31, 36, 53, 77, 84]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 44/44\n",
      "\n",
      "TEST #45:\n",
      "Before sorting: [-3, -59, 40, 28, -91, -75, 35, -89, -59, 58, 9, 15, 49, -56, -62, 48, 41, 100, 99, -48, -20, -35, -26, -19, 27]\n",
      "After sorting: [-91, -89, -75, -62, -59, -59, -56, -48, -35, -26, -20, -19, -3, 9, 15, 27, 28, 35, 40, 41, 48, 49, 58, 99, 100]\n",
      "Expected result: [-91, -89, -75, -62, -59, -59, -56, -48, -35, -26, -20, -19, -3, 9, 15, 27, 28, 35, 40, 41, 48, 49, 58, 99, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 45/45\n",
      "\n",
      "TEST #46:\n",
      "Before sorting: [10, 48, -89, -36, -98, -35, -39, -66, 99, -14, 73, 17, -26, -71, 18, 85, -89, -10, 81]\n",
      "After sorting: [-98, -89, -89, -71, -66, -39, -36, -35, -26, -14, -10, 10, 17, 18, 48, 73, 81, 85, 99]\n",
      "Expected result: [-98, -89, -89, -71, -66, -39, -36, -35, -26, -14, -10, 10, 17, 18, 48, 73, 81, 85, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 46/46\n",
      "\n",
      "TEST #47:\n",
      "Before sorting: []\n",
      "After sorting: []\n",
      "Expected result: []\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 47/47\n",
      "\n",
      "TEST #48:\n",
      "Before sorting: []\n",
      "After sorting: []\n",
      "Expected result: []\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 48/48\n",
      "\n",
      "TEST #49:\n",
      "Before sorting: [89, 61, 58, 32, 48, -34, 32, 56, -61, 24, -39, 29, 22, -80, -61]\n",
      "After sorting: [-80, -61, -61, -39, -34, 22, 24, 29, 32, 32, 48, 56, 58, 61, 89]\n",
      "Expected result: [-80, -61, -61, -39, -34, 22, 24, 29, 32, 32, 48, 56, 58, 61, 89]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 49/49\n",
      "\n",
      "TEST #50:\n",
      "Before sorting: [40, -9, -2, 20, 8, -69, 91, -64, 86, 86, 2, 46, 67, 84, 75, -33, -77, -54, -49, 40, 55, -6, 36, 28, 91, 90, -44, 39, 49, -56, -21, -39, 8, 100, 62, 1, 74, 88]\n",
      "After sorting: [-77, -69, -64, -56, -54, -49, -44, -39, -33, -21, -9, -6, -2, 1, 2, 8, 8, 20, 28, 36, 39, 40, 40, 46, 49, 55, 62, 67, 74, 75, 84, 86, 86, 88, 90, 91, 91, 100]\n",
      "Expected result: [-77, -69, -64, -56, -54, -49, -44, -39, -33, -21, -9, -6, -2, 1, 2, 8, 8, 20, 28, 36, 39, 40, 40, 46, 49, 55, 62, 67, 74, 75, 84, 86, 86, 88, 90, 91, 91, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 50/50\n",
      "\n",
      "TEST #51:\n",
      "Before sorting: [41]\n",
      "After sorting: [41]\n",
      "Expected result: [41]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 51/51\n",
      "\n",
      "TEST #52:\n",
      "Before sorting: [-100, 24, 85, 55, 97, 71, 0, -100, 34, 68, -43, 87, 66, -90, -31, -56, -88, -26, 29, 61, 73, -6]\n",
      "After sorting: [-100, -100, -90, -88, -56, -43, -31, -26, -6, 0, 24, 29, 34, 55, 61, 66, 68, 71, 73, 85, 87, 97]\n",
      "Expected result: [-100, -100, -90, -88, -56, -43, -31, -26, -6, 0, 24, 29, 34, 55, 61, 66, 68, 71, 73, 85, 87, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 52/52\n",
      "\n",
      "TEST #53:\n",
      "Before sorting: [0, 0, 11, 38, -98, -14, 46, -79, 38, 11, 93, 59, -72, -82, -29, 51, 99, 36, -15, -61, -6, 79, -30, -66, -32, 94, 78, 100, -64, -91, 44, -7, -95, -85, -20]\n",
      "After sorting: [-98, -95, -91, -85, -82, -79, -72, -66, -64, -61, -32, -30, -29, -20, -15, -14, -7, -6, 0, 0, 11, 11, 36, 38, 38, 44, 46, 51, 59, 78, 79, 93, 94, 99, 100]\n",
      "Expected result: [-98, -95, -91, -85, -82, -79, -72, -66, -64, -61, -32, -30, -29, -20, -15, -14, -7, -6, 0, 0, 11, 11, 36, 38, 38, 44, 46, 51, 59, 78, 79, 93, 94, 99, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 53/53\n",
      "\n",
      "TEST #54:\n",
      "Before sorting: [-86, -9, -19, 48, -70, -49, -48, -8, 0, 76, -38, -54, 16, 12, -82, 54, -28, -94, 77]\n",
      "After sorting: [-94, -86, -82, -70, -54, -49, -48, -38, -28, -19, -9, -8, 0, 12, 16, 48, 54, 76, 77]\n",
      "Expected result: [-94, -86, -82, -70, -54, -49, -48, -38, -28, -19, -9, -8, 0, 12, 16, 48, 54, 76, 77]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 54/54\n",
      "\n",
      "TEST #55:\n",
      "Before sorting: [-37, 3, -96, 23, 81, 50, 87, 94, -20]\n",
      "After sorting: [-96, -37, -20, 3, 23, 50, 81, 87, 94]\n",
      "Expected result: [-96, -37, -20, 3, 23, 50, 81, 87, 94]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 55/55\n",
      "\n",
      "TEST #56:\n",
      "Before sorting: [37, 56, -42, -20, 84, -73, 92, -98, 51, -39, 82, -62, 0, 39, -85, 81, -67, -72, 50, -12, -49, -93, 85, 41, 21, 65, 31, -35, 55, 84, -39]\n",
      "After sorting: [-98, -93, -85, -73, -72, -67, -62, -49, -42, -39, -39, -35, -20, -12, 0, 21, 31, 37, 39, 41, 50, 51, 55, 56, 65, 81, 82, 84, 84, 85, 92]\n",
      "Expected result: [-98, -93, -85, -73, -72, -67, -62, -49, -42, -39, -39, -35, -20, -12, 0, 21, 31, 37, 39, 41, 50, 51, 55, 56, 65, 81, 82, 84, 84, 85, 92]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 56/56\n",
      "\n",
      "TEST #57:\n",
      "Before sorting: [95, -21, 34, -49, -72, 85, 100, -92, -92, -57, 66, -84, -48, -75, -73, 60, 56, -91, 47, -58, 26, 37, 16, -1, -72, 31, 81, -30, 88, -89, 77, 61, 6, -97, -32, 94, 62, -60]\n",
      "After sorting: [-97, -92, -92, -91, -89, -84, -75, -73, -72, -72, -60, -58, -57, -49, -48, -32, -30, -21, -1, 6, 16, 26, 31, 34, 37, 47, 56, 60, 61, 62, 66, 77, 81, 85, 88, 94, 95, 100]\n",
      "Expected result: [-97, -92, -92, -91, -89, -84, -75, -73, -72, -72, -60, -58, -57, -49, -48, -32, -30, -21, -1, 6, 16, 26, 31, 34, 37, 47, 56, 60, 61, 62, 66, 77, 81, 85, 88, 94, 95, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 57/57\n",
      "\n",
      "TEST #58:\n",
      "Before sorting: [72, 10, 4, -85, -31, -38, -67, -54, -66, -39, 78, -30, -80, -90, -36, 90, -96]\n",
      "After sorting: [-96, -90, -85, -80, -67, -66, -54, -39, -38, -36, -31, -30, 4, 10, 72, 78, 90]\n",
      "Expected result: [-96, -90, -85, -80, -67, -66, -54, -39, -38, -36, -31, -30, 4, 10, 72, 78, 90]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 58/58\n",
      "\n",
      "TEST #59:\n",
      "Before sorting: [22, 39, -94, -30, 70, -6, 65, -15, -73, -78, -54, 19, 57, 94, 37, 33, 94, 1, -35, -55, 68, 43, -36, 72, 27, 15, -49, 26, -53, -45, -44, -95, 58, 29, 59, -88, -2, -99, 99, -39, -24, -25, 14]\n",
      "After sorting: [-99, -95, -94, -88, -78, -73, -55, -54, -53, -49, -45, -44, -39, -36, -35, -30, -25, -24, -15, -6, -2, 1, 14, 15, 19, 22, 26, 27, 29, 33, 37, 39, 43, 57, 58, 59, 65, 68, 70, 72, 94, 94, 99]\n",
      "Expected result: [-99, -95, -94, -88, -78, -73, -55, -54, -53, -49, -45, -44, -39, -36, -35, -30, -25, -24, -15, -6, -2, 1, 14, 15, 19, 22, 26, 27, 29, 33, 37, 39, 43, 57, 58, 59, 65, 68, 70, 72, 94, 94, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 59/59\n",
      "\n",
      "TEST #60:\n",
      "Before sorting: [-60, 62, 60, -63, 42, 45, 80, 95, 39, -6, 76, -57, -26, -67, 67, 37, -12, 20, 32, 31, -76, -19, 79, 44, -41, -36, 43, 17, 94, -56, -66, -36, 10]\n",
      "After sorting: [-76, -67, -66, -63, -60, -57, -56, -41, -36, -36, -26, -19, -12, -6, 10, 17, 20, 31, 32, 37, 39, 42, 43, 44, 45, 60, 62, 67, 76, 79, 80, 94, 95]\n",
      "Expected result: [-76, -67, -66, -63, -60, -57, -56, -41, -36, -36, -26, -19, -12, -6, 10, 17, 20, 31, 32, 37, 39, 42, 43, 44, 45, 60, 62, 67, 76, 79, 80, 94, 95]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 60/60\n",
      "\n",
      "TEST #61:\n",
      "Before sorting: [28, -92, -85, -52, 31, 47, -44, 87, -29, 29, 3, -49, 53, -13, -17, -97, 86, -66, 16, 29, 4, 77, -51, 29, -53]\n",
      "After sorting: [-97, -92, -85, -66, -53, -52, -51, -49, -44, -29, -17, -13, 3, 4, 16, 28, 29, 29, 29, 31, 47, 53, 77, 86, 87]\n",
      "Expected result: [-97, -92, -85, -66, -53, -52, -51, -49, -44, -29, -17, -13, 3, 4, 16, 28, 29, 29, 29, 31, 47, 53, 77, 86, 87]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 61/61\n",
      "\n",
      "TEST #62:\n",
      "Before sorting: [77, -77]\n",
      "After sorting: [-77, 77]\n",
      "Expected result: [-77, 77]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 62/62\n",
      "\n",
      "TEST #63:\n",
      "Before sorting: [-94, 59, 8, 68, -70, -29, 1, 6, 39, -99, 16, 73, -18, -76, -31, 70, 6, 1, -79, -44, 3, -29, -77, -41, 39, 93, 66, 66, 83, 40, 37, 53, 9, 99, -87, 54, 63, 69, 39, 67, 90, 89, -34]\n",
      "After sorting: [-99, -94, -87, -79, -77, -76, -70, -44, -41, -34, -31, -29, -29, -18, 1, 1, 3, 6, 6, 8, 9, 16, 37, 39, 39, 39, 40, 53, 54, 59, 63, 66, 66, 67, 68, 69, 70, 73, 83, 89, 90, 93, 99]\n",
      "Expected result: [-99, -94, -87, -79, -77, -76, -70, -44, -41, -34, -31, -29, -29, -18, 1, 1, 3, 6, 6, 8, 9, 16, 37, 39, 39, 39, 40, 53, 54, 59, 63, 66, 66, 67, 68, 69, 70, 73, 83, 89, 90, 93, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 63/63\n",
      "\n",
      "TEST #64:\n",
      "Before sorting: [58, 67, -1, 99, -29, 49, 76, -26, 23, 42, 10, -59, -75, -29, -59, 81, 31, 99, -83, 68, -19, 39, 65, 66, -86, 72, 81, 62, 49]\n",
      "After sorting: [-86, -83, -75, -59, -59, -29, -29, -26, -19, -1, 10, 23, 31, 39, 42, 49, 49, 58, 62, 65, 66, 67, 68, 72, 76, 81, 81, 99, 99]\n",
      "Expected result: [-86, -83, -75, -59, -59, -29, -29, -26, -19, -1, 10, 23, 31, 39, 42, 49, 49, 58, 62, 65, 66, 67, 68, 72, 76, 81, 81, 99, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 64/64\n",
      "\n",
      "TEST #65:\n",
      "Before sorting: [-52, 57, 96, -47, -57, 43, -34, 66, -37, -94, 64, 74, -16, 7, 29, -4, -31, -46, -100, -59, 8, -62, 23, -26, -29, -53, 50, -81, -20, 94, 23, -95, 13, 5, -8, 1, 34, 97, 8, 36, -55, -58, -24, -43, -94, -49, -16, -43, -26]\n",
      "After sorting: [-100, -95, -94, -94, -81, -62, -59, -58, -57, -55, -53, -52, -49, -47, -46, -43, -43, -37, -34, -31, -29, -26, -26, -24, -20, -16, -16, -8, -4, 1, 5, 7, 8, 8, 13, 23, 23, 29, 34, 36, 43, 50, 57, 64, 66, 74, 94, 96, 97]\n",
      "Expected result: [-100, -95, -94, -94, -81, -62, -59, -58, -57, -55, -53, -52, -49, -47, -46, -43, -43, -37, -34, -31, -29, -26, -26, -24, -20, -16, -16, -8, -4, 1, 5, 7, 8, 8, 13, 23, 23, 29, 34, 36, 43, 50, 57, 64, 66, 74, 94, 96, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 65/65\n",
      "\n",
      "TEST #66:\n",
      "Before sorting: [62, 23, -34, 88, -99, -26, -61, -77, 66, -92, 91, -74, -83, -4, -78, -76, -62, 86, 0, -34, -66, -59, 26, -12, 81]\n",
      "After sorting: [-99, -92, -83, -78, -77, -76, -74, -66, -62, -61, -59, -34, -34, -26, -12, -4, 0, 23, 26, 62, 66, 81, 86, 88, 91]\n",
      "Expected result: [-99, -92, -83, -78, -77, -76, -74, -66, -62, -61, -59, -34, -34, -26, -12, -4, 0, 23, 26, 62, 66, 81, 86, 88, 91]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 66/66\n",
      "\n",
      "TEST #67:\n",
      "Before sorting: [2, 4, -74, 2, 8, 40, -8, 78, 10, 85, -34, -82, 56, 39, 32, 9, 53, -55]\n",
      "After sorting: [-82, -74, -55, -34, -8, 2, 2, 4, 8, 9, 10, 32, 39, 40, 53, 56, 78, 85]\n",
      "Expected result: [-82, -74, -55, -34, -8, 2, 2, 4, 8, 9, 10, 32, 39, 40, 53, 56, 78, 85]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 67/67\n",
      "\n",
      "TEST #68:\n",
      "Before sorting: [-33, -18, 34, -40, -38, -45, -91, -44, 34, 60, 30, 67, 51, 100, -37, 77, 82, 24, 39, 54, -8, -7, 48, 63, -97, -89, -73, 65, -70, 55, -51, 5]\n",
      "After sorting: [-97, -91, -89, -73, -70, -51, -45, -44, -40, -38, -37, -33, -18, -8, -7, 5, 24, 30, 34, 34, 39, 48, 51, 54, 55, 60, 63, 65, 67, 77, 82, 100]\n",
      "Expected result: [-97, -91, -89, -73, -70, -51, -45, -44, -40, -38, -37, -33, -18, -8, -7, 5, 24, 30, 34, 34, 39, 48, 51, 54, 55, 60, 63, 65, 67, 77, 82, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 68/68\n",
      "\n",
      "TEST #69:\n",
      "Before sorting: [49, -99, -49, -15, -88, 39, -52, -44, 43, -35, 86, -37, -94, -83, 68, 3, -26, -46, -43, -67, 87, 74, -80, 73, -29, 81, -100, 85, -71, -95, -60, -53, -41, -86]\n",
      "After sorting: [-100, -99, -95, -94, -88, -86, -83, -80, -71, -67, -60, -53, -52, -49, -46, -44, -43, -41, -37, -35, -29, -26, -15, 3, 39, 43, 49, 68, 73, 74, 81, 85, 86, 87]\n",
      "Expected result: [-100, -99, -95, -94, -88, -86, -83, -80, -71, -67, -60, -53, -52, -49, -46, -44, -43, -41, -37, -35, -29, -26, -15, 3, 39, 43, 49, 68, 73, 74, 81, 85, 86, 87]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 69/69\n",
      "\n",
      "TEST #70:\n",
      "Before sorting: [-69, -95, 66, -39, -69, 61, 79, -52, 34, -32, 78, -14, 72, 79, 24, -28, -74, 12, -12, -13, 56, -40, -21, -38, 73, -8, -86, -4, -18, -71, -81, -80, -77, -23, -1, 86, 3, -51, 97, -93, 75, 29, 35, -86, -87, -42, -63, -94, -94]\n",
      "After sorting: [-95, -94, -94, -93, -87, -86, -86, -81, -80, -77, -74, -71, -69, -69, -63, -52, -51, -42, -40, -39, -38, -32, -28, -23, -21, -18, -14, -13, -12, -8, -4, -1, 3, 12, 24, 29, 34, 35, 56, 61, 66, 72, 73, 75, 78, 79, 79, 86, 97]\n",
      "Expected result: [-95, -94, -94, -93, -87, -86, -86, -81, -80, -77, -74, -71, -69, -69, -63, -52, -51, -42, -40, -39, -38, -32, -28, -23, -21, -18, -14, -13, -12, -8, -4, -1, 3, 12, 24, 29, 34, 35, 56, 61, 66, 72, 73, 75, 78, 79, 79, 86, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 70/70\n",
      "\n",
      "TEST #71:\n",
      "Before sorting: [-16, 64, 51, 53, -60, 93, -53, -49, 34, 88, 74, -29, 58, 77, -57, 83, -73, -4, 49, -52, 24, -27, -62, -20, 48, -84, 19, 88, 34, 43, -98, 47, -2, -60, -97, -73, 57, 15, 85, 34, 19, -93, 73, 72, -81, 20, 35, -18, 9]\n",
      "After sorting: [-98, -97, -93, -84, -81, -73, -73, -62, -60, -60, -57, -53, -52, -49, -29, -27, -20, -18, -16, -4, -2, 9, 15, 19, 19, 20, 24, 34, 34, 34, 35, 43, 47, 48, 49, 51, 53, 57, 58, 64, 72, 73, 74, 77, 83, 85, 88, 88, 93]\n",
      "Expected result: [-98, -97, -93, -84, -81, -73, -73, -62, -60, -60, -57, -53, -52, -49, -29, -27, -20, -18, -16, -4, -2, 9, 15, 19, 19, 20, 24, 34, 34, 34, 35, 43, 47, 48, 49, 51, 53, 57, 58, 64, 72, 73, 74, 77, 83, 85, 88, 88, 93]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 71/71\n",
      "\n",
      "TEST #72:\n",
      "Before sorting: [44, 66, -45, 2, 68, -42, 42, 65, -48, 35]\n",
      "After sorting: [-48, -45, -42, 2, 35, 42, 44, 65, 66, 68]\n",
      "Expected result: [-48, -45, -42, 2, 35, 42, 44, 65, 66, 68]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 72/72\n",
      "\n",
      "TEST #73:\n",
      "Before sorting: [100, 27, 92, -46, -18]\n",
      "After sorting: [-46, -18, 27, 92, 100]\n",
      "Expected result: [-46, -18, 27, 92, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 73/73\n",
      "\n",
      "TEST #74:\n",
      "Before sorting: [-36, 95, -94, 60, 20, -5, 9, 39]\n",
      "After sorting: [-94, -36, -5, 9, 20, 39, 60, 95]\n",
      "Expected result: [-94, -36, -5, 9, 20, 39, 60, 95]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 74/74\n",
      "\n",
      "TEST #75:\n",
      "Before sorting: [72, 78, -77, -91, 34, -33, -98, -95, 30, 9, 29, -24, 3, -14, 7, 64, -31, 84, -13, -23, 43, 30, -35, 38, 26, -9, 68, 0, 73, 28, 36, 76, -29, 17, 69, 22, 32, -24, -47, -36, 51]\n",
      "After sorting: [-98, -95, -91, -77, -47, -36, -35, -33, -31, -29, -24, -24, -23, -14, -13, -9, 0, 3, 7, 9, 17, 22, 26, 28, 29, 30, 30, 32, 34, 36, 38, 43, 51, 64, 68, 69, 72, 73, 76, 78, 84]\n",
      "Expected result: [-98, -95, -91, -77, -47, -36, -35, -33, -31, -29, -24, -24, -23, -14, -13, -9, 0, 3, 7, 9, 17, 22, 26, 28, 29, 30, 30, 32, 34, 36, 38, 43, 51, 64, 68, 69, 72, 73, 76, 78, 84]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 75/75\n",
      "\n",
      "TEST #76:\n",
      "Before sorting: [-48, 50, 25, 56, 10, 92, 90, -93, -68, -38, 65, -97, -88, 22, 19, 23, -33]\n",
      "After sorting: [-97, -93, -88, -68, -48, -38, -33, 10, 19, 22, 23, 25, 50, 56, 65, 90, 92]\n",
      "Expected result: [-97, -93, -88, -68, -48, -38, -33, 10, 19, 22, 23, 25, 50, 56, 65, 90, 92]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 76/76\n",
      "\n",
      "TEST #77:\n",
      "Before sorting: [-97, 15, 2, -89, -36, -88, -42, 96, 17, 34, 51, 36, 36, -13, -75]\n",
      "After sorting: [-97, -89, -88, -75, -42, -36, -13, 2, 15, 17, 34, 36, 36, 51, 96]\n",
      "Expected result: [-97, -89, -88, -75, -42, -36, -13, 2, 15, 17, 34, 36, 36, 51, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 77/77\n",
      "\n",
      "TEST #78:\n",
      "Before sorting: [-53, -63, 0, -71, 47, 36, -48, 20, -69, -69, -79, 18, -100, 23, -38, -80, -60, -48, 17, 42, 43, -47, -82, -49, 50, -81, -2, -83]\n",
      "After sorting: [-100, -83, -82, -81, -80, -79, -71, -69, -69, -63, -60, -53, -49, -48, -48, -47, -38, -2, 0, 17, 18, 20, 23, 36, 42, 43, 47, 50]\n",
      "Expected result: [-100, -83, -82, -81, -80, -79, -71, -69, -69, -63, -60, -53, -49, -48, -48, -47, -38, -2, 0, 17, 18, 20, 23, 36, 42, 43, 47, 50]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 78/78\n",
      "\n",
      "TEST #79:\n",
      "Before sorting: [27, -31, 68, -43, 7, -23, 11, -65, -89]\n",
      "After sorting: [-89, -65, -43, -31, -23, 7, 11, 27, 68]\n",
      "Expected result: [-89, -65, -43, -31, -23, 7, 11, 27, 68]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 79/79\n",
      "\n",
      "TEST #80:\n",
      "Before sorting: [97, 91, 89, 75, -19, -79, -95, 22, -32, 7, -35, -58, -79, -47, 73, 35, 1, -38, 8, -48, -22, -45, -27, 0, 30, -33, -65, -17, -91, -65, 12, -80, -47, 13, 71, -24, -39, -98, 82]\n",
      "After sorting: [-98, -95, -91, -80, -79, -79, -65, -65, -58, -48, -47, -47, -45, -39, -38, -35, -33, -32, -27, -24, -22, -19, -17, 0, 1, 7, 8, 12, 13, 22, 30, 35, 71, 73, 75, 82, 89, 91, 97]\n",
      "Expected result: [-98, -95, -91, -80, -79, -79, -65, -65, -58, -48, -47, -47, -45, -39, -38, -35, -33, -32, -27, -24, -22, -19, -17, 0, 1, 7, 8, 12, 13, 22, 30, 35, 71, 73, 75, 82, 89, 91, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 80/80\n",
      "\n",
      "TEST #81:\n",
      "Before sorting: [-36, -59, -84, 0, 30, 82, 14, 87, -52, 34, -27, -5, 5, -5, 1]\n",
      "After sorting: [-84, -59, -52, -36, -27, -5, -5, 0, 1, 5, 14, 30, 34, 82, 87]\n",
      "Expected result: [-84, -59, -52, -36, -27, -5, -5, 0, 1, 5, 14, 30, 34, 82, 87]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 81/81\n",
      "\n",
      "TEST #82:\n",
      "Before sorting: [29, -48, -66, -58, -80, -15, -15, -76, 79, 53, 49, -85, -16, 100, -36, 3, 94, 30, 63, -26, -39, 28, 64, -27, -30, 77, -65, -100, -4, -78, -34, -30]\n",
      "After sorting: [-100, -85, -80, -78, -76, -66, -65, -58, -48, -39, -36, -34, -30, -30, -27, -26, -16, -15, -15, -4, 3, 28, 29, 30, 49, 53, 63, 64, 77, 79, 94, 100]\n",
      "Expected result: [-100, -85, -80, -78, -76, -66, -65, -58, -48, -39, -36, -34, -30, -30, -27, -26, -16, -15, -15, -4, 3, 28, 29, 30, 49, 53, 63, 64, 77, 79, 94, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 82/82\n",
      "\n",
      "TEST #83:\n",
      "Before sorting: [99, 1, 90, 21, 15, -1, 8, -86, 20, -83, 31, -22, 40, 70, -2, -61, 30, 14, 49, 40, -84, 98, 68, 49, -30, -80, 91, 53, -35, 40, 31, 91, 53, -100, 29, 53, 64, -69, -70, 56, 100, 74, 45, -54, 11, 77, -10, -61, -17]\n",
      "After sorting: [-100, -86, -84, -83, -80, -70, -69, -61, -61, -54, -35, -30, -22, -17, -10, -2, -1, 1, 8, 11, 14, 15, 20, 21, 29, 30, 31, 31, 40, 40, 40, 45, 49, 49, 53, 53, 53, 56, 64, 68, 70, 74, 77, 90, 91, 91, 98, 99, 100]\n",
      "Expected result: [-100, -86, -84, -83, -80, -70, -69, -61, -61, -54, -35, -30, -22, -17, -10, -2, -1, 1, 8, 11, 14, 15, 20, 21, 29, 30, 31, 31, 40, 40, 40, 45, 49, 49, 53, 53, 53, 56, 64, 68, 70, 74, 77, 90, 91, 91, 98, 99, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 83/83\n",
      "\n",
      "TEST #84:\n",
      "Before sorting: [4, 66, -26, -53, -51, -22, -19, -89, -80, -93, 72, 23, 65, 18, 41, -61, -57, 100, -89, 12, -100, 35, -52, 13, -85]\n",
      "After sorting: [-100, -93, -89, -89, -85, -80, -61, -57, -53, -52, -51, -26, -22, -19, 4, 12, 13, 18, 23, 35, 41, 65, 66, 72, 100]\n",
      "Expected result: [-100, -93, -89, -89, -85, -80, -61, -57, -53, -52, -51, -26, -22, -19, 4, 12, 13, 18, 23, 35, 41, 65, 66, 72, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 84/84\n",
      "\n",
      "TEST #85:\n",
      "Before sorting: [33, -9, 29, 20, 95, 82, -60, 99, -48, 90, 43, -31, 69, 34, 82, -88, 1, -96, 51, 11, -45, -65, -64, -83, 14, -39, -38, 97, -5, -95, 4, -96, -3, -30, -80]\n",
      "After sorting: [-96, -96, -95, -88, -83, -80, -65, -64, -60, -48, -45, -39, -38, -31, -30, -9, -5, -3, 1, 4, 11, 14, 20, 29, 33, 34, 43, 51, 69, 82, 82, 90, 95, 97, 99]\n",
      "Expected result: [-96, -96, -95, -88, -83, -80, -65, -64, -60, -48, -45, -39, -38, -31, -30, -9, -5, -3, 1, 4, 11, 14, 20, 29, 33, 34, 43, 51, 69, 82, 82, 90, 95, 97, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 85/85\n",
      "\n",
      "TEST #86:\n",
      "Before sorting: [-30, -16, -26, 60, 2, -25, -93, -2, 99, -29, 16, -82, 11, -22, 24, 44, -99, 94, -44, 99, 16, 22, -31, -43, 27, 7, 17, 10, 38]\n",
      "After sorting: [-99, -93, -82, -44, -43, -31, -30, -29, -26, -25, -22, -16, -2, 2, 7, 10, 11, 16, 16, 17, 22, 24, 27, 38, 44, 60, 94, 99, 99]\n",
      "Expected result: [-99, -93, -82, -44, -43, -31, -30, -29, -26, -25, -22, -16, -2, 2, 7, 10, 11, 16, 16, 17, 22, 24, 27, 38, 44, 60, 94, 99, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 86/86\n",
      "\n",
      "TEST #87:\n",
      "Before sorting: [-64, -50, 13]\n",
      "After sorting: [-64, -50, 13]\n",
      "Expected result: [-64, -50, 13]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 87/87\n",
      "\n",
      "TEST #88:\n",
      "Before sorting: [-50, -8, -31, 53, 44, 52, 5, -62, -12, -52, 34, -29, 88, -33, -96, -29, -81, 1, -76, 86, 40, 86, -70, 59, -2, 90, 51, 12, -93, 1, 67, -50]\n",
      "After sorting: [-96, -93, -81, -76, -70, -62, -52, -50, -50, -33, -31, -29, -29, -12, -8, -2, 1, 1, 5, 12, 34, 40, 44, 51, 52, 53, 59, 67, 86, 86, 88, 90]\n",
      "Expected result: [-96, -93, -81, -76, -70, -62, -52, -50, -50, -33, -31, -29, -29, -12, -8, -2, 1, 1, 5, 12, 34, 40, 44, 51, 52, 53, 59, 67, 86, 86, 88, 90]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 88/88\n",
      "\n",
      "TEST #89:\n",
      "Before sorting: [62, 10, 10, -33, -60, -94, 54, 53]\n",
      "After sorting: [-94, -60, -33, 10, 10, 53, 54, 62]\n",
      "Expected result: [-94, -60, -33, 10, 10, 53, 54, 62]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 89/89\n",
      "\n",
      "TEST #90:\n",
      "Before sorting: [-58, -90, 69, -68, -6, 36, 20, -6, -67, 21, -45, 17, -74, -2, 26, -85, 83, -12, -96, 96, -96, -65, 26, -93, -35, -37, 42, 90, 100, -3, 45, 36, -47, -98, 58, 32, -37, 41, 43]\n",
      "After sorting: [-98, -96, -96, -93, -90, -85, -74, -68, -67, -65, -58, -47, -45, -37, -37, -35, -12, -6, -6, -3, -2, 17, 20, 21, 26, 26, 32, 36, 36, 41, 42, 43, 45, 58, 69, 83, 90, 96, 100]\n",
      "Expected result: [-98, -96, -96, -93, -90, -85, -74, -68, -67, -65, -58, -47, -45, -37, -37, -35, -12, -6, -6, -3, -2, 17, 20, 21, 26, 26, 32, 36, 36, 41, 42, 43, 45, 58, 69, 83, 90, 96, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 90/90\n",
      "\n",
      "TEST #91:\n",
      "Before sorting: [-11, 58, -30, 84, 33, -80, -17, 100, 77, -25, -46, 83, -42, -36, 2, -79, -22, 66, -66, -48, 56, 87, 74, 84, -46, 2, 55, -12, 82, -53, 68, -58, -80, -65]\n",
      "After sorting: [-80, -80, -79, -66, -65, -58, -53, -48, -46, -46, -42, -36, -30, -25, -22, -17, -12, -11, 2, 2, 33, 55, 56, 58, 66, 68, 74, 77, 82, 83, 84, 84, 87, 100]\n",
      "Expected result: [-80, -80, -79, -66, -65, -58, -53, -48, -46, -46, -42, -36, -30, -25, -22, -17, -12, -11, 2, 2, 33, 55, 56, 58, 66, 68, 74, 77, 82, 83, 84, 84, 87, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 91/91\n",
      "\n",
      "TEST #92:\n",
      "Before sorting: [-61, -90, -57, 95, -64, -65, -90, -51, -7, -17, -9, 13, 65, 53, -62, -55, 9, -24, 44, 15, 35, -45, -82, 30, 22, -52, 62, 1, 6, 89, -69, 5, 91, -94, -64, 98, -65, -51, -48, -58, -29, -81, -26, -41]\n",
      "After sorting: [-94, -90, -90, -82, -81, -69, -65, -65, -64, -64, -62, -61, -58, -57, -55, -52, -51, -51, -48, -45, -41, -29, -26, -24, -17, -9, -7, 1, 5, 6, 9, 13, 15, 22, 30, 35, 44, 53, 62, 65, 89, 91, 95, 98]\n",
      "Expected result: [-94, -90, -90, -82, -81, -69, -65, -65, -64, -64, -62, -61, -58, -57, -55, -52, -51, -51, -48, -45, -41, -29, -26, -24, -17, -9, -7, 1, 5, 6, 9, 13, 15, 22, 30, 35, 44, 53, 62, 65, 89, 91, 95, 98]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 92/92\n",
      "\n",
      "TEST #93:\n",
      "Before sorting: [-35, 64, -80, 26, 42, 90, -19, -11, 96, 44, -47, 86, 30, 95, 81, -6, 32, -49, 86, -87, -24, 64, 17, -46, 64]\n",
      "After sorting: [-87, -80, -49, -47, -46, -35, -24, -19, -11, -6, 17, 26, 30, 32, 42, 44, 64, 64, 64, 81, 86, 86, 90, 95, 96]\n",
      "Expected result: [-87, -80, -49, -47, -46, -35, -24, -19, -11, -6, 17, 26, 30, 32, 42, 44, 64, 64, 64, 81, 86, 86, 90, 95, 96]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 93/93\n",
      "\n",
      "TEST #94:\n",
      "Before sorting: [8, 32, 71, 10, 81, 18, -46, -88, 51, 89, -88, -35, 14, 63, -59, 60, 48, 74, -29, 85, -74, -71, 48, 59, -42, 57, 36, -90, -32, 24, 73, -32, -45, 52, -60, -50, 42, -40, 5, -63, 87, -1, -39, -35, 97, -7, 72, 12, 41, -81]\n",
      "After sorting: [-90, -88, -88, -81, -74, -71, -63, -60, -59, -50, -46, -45, -42, -40, -39, -35, -35, -32, -32, -29, -7, -1, 5, 8, 10, 12, 14, 18, 24, 32, 36, 41, 42, 48, 48, 51, 52, 57, 59, 60, 63, 71, 72, 73, 74, 81, 85, 87, 89, 97]\n",
      "Expected result: [-90, -88, -88, -81, -74, -71, -63, -60, -59, -50, -46, -45, -42, -40, -39, -35, -35, -32, -32, -29, -7, -1, 5, 8, 10, 12, 14, 18, 24, 32, 36, 41, 42, 48, 48, 51, 52, 57, 59, 60, 63, 71, 72, 73, 74, 81, 85, 87, 89, 97]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 94/94\n",
      "\n",
      "TEST #95:\n",
      "Before sorting: [-15, 21, -57, 65, 99, 0, -100, -17, -90, 52, 5, 37, -77, 8, 73, 69, -27, 49, -56, -27, -57, 59, 98, -10, -69, -16, -75, -36, 2, 40, -25, 69, -46, 35, 78, 98, -87, 58, 27, 93, -70, 37, -4, 71, 63, 45, -37]\n",
      "After sorting: [-100, -90, -87, -77, -75, -70, -69, -57, -57, -56, -46, -37, -36, -27, -27, -25, -17, -16, -15, -10, -4, 0, 2, 5, 8, 21, 27, 35, 37, 37, 40, 45, 49, 52, 58, 59, 63, 65, 69, 69, 71, 73, 78, 93, 98, 98, 99]\n",
      "Expected result: [-100, -90, -87, -77, -75, -70, -69, -57, -57, -56, -46, -37, -36, -27, -27, -25, -17, -16, -15, -10, -4, 0, 2, 5, 8, 21, 27, 35, 37, 37, 40, 45, 49, 52, 58, 59, 63, 65, 69, 69, 71, 73, 78, 93, 98, 98, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 95/95\n",
      "\n",
      "TEST #96:\n",
      "Before sorting: []\n",
      "After sorting: []\n",
      "Expected result: []\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 96/96\n",
      "\n",
      "TEST #97:\n",
      "Before sorting: [-84, -18, -70, -88, 100, -88, 39, -25, -36, 71, -45, 40, 5, 75, -98, 39, 77, 56, 9, 88, -78, -31, -86, 14]\n",
      "After sorting: [-98, -88, -88, -86, -84, -78, -70, -45, -36, -31, -25, -18, 5, 9, 14, 39, 39, 40, 56, 71, 75, 77, 88, 100]\n",
      "Expected result: [-98, -88, -88, -86, -84, -78, -70, -45, -36, -31, -25, -18, 5, 9, 14, 39, 39, 40, 56, 71, 75, 77, 88, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 97/97\n",
      "\n",
      "TEST #98:\n",
      "Before sorting: [82, 62, 88, 100, -86, 84, -84, 31, 5, -36, 81, 52, 2, 38, 45, -91, 74, 26, -79, 60, 70, 74, -38, 28, -16, 4, -53, -15, 14, 83, 57, 69, -76, 82, 86, 73, -13, 44, 90]\n",
      "After sorting: [-91, -86, -84, -79, -76, -53, -38, -36, -16, -15, -13, 2, 4, 5, 14, 26, 28, 31, 38, 44, 45, 52, 57, 60, 62, 69, 70, 73, 74, 74, 81, 82, 82, 83, 84, 86, 88, 90, 100]\n",
      "Expected result: [-91, -86, -84, -79, -76, -53, -38, -36, -16, -15, -13, 2, 4, 5, 14, 26, 28, 31, 38, 44, 45, 52, 57, 60, 62, 69, 70, 73, 74, 74, 81, 82, 82, 83, 84, 86, 88, 90, 100]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 98/98\n",
      "\n",
      "TEST #99:\n",
      "Before sorting: [99, -25, -82, -58, -92]\n",
      "After sorting: [-92, -82, -58, -25, 99]\n",
      "Expected result: [-92, -82, -58, -25, 99]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 99/99\n",
      "\n",
      "TEST #100:\n",
      "Before sorting: [-14, 24, 22, 16, 1, 83, -39, -97, 76, 29, -9, 39, -83, -61, -70, 91, -60, -18, 67, 36, 9, 89, 4, 35, -25, 5, 73, -63, -80, 76, 3, -29, 48, 58, 65, 43, 32, 83, 37, -88, -49, -72]\n",
      "After sorting: [-97, -88, -83, -80, -72, -70, -63, -61, -60, -49, -39, -29, -25, -18, -14, -9, 1, 3, 4, 5, 9, 16, 22, 24, 29, 32, 35, 36, 37, 39, 43, 48, 58, 65, 67, 73, 76, 76, 83, 83, 89, 91]\n",
      "Expected result: [-97, -88, -83, -80, -72, -70, -63, -61, -60, -49, -39, -29, -25, -18, -14, -9, 1, 3, 4, 5, 9, 16, 22, 24, 29, 32, 35, 36, 37, 39, 43, 48, 58, 65, 67, 73, 76, 76, 83, 83, 89, 91]\n",
      "Test PASSED\n",
      "Current passed-to-tested ratio: 100/100\n",
      "\n",
      "Sorting algorithms is correct\n",
      "Passed tests in total: 100/100\n"
     ]
    }
   ],
   "source": [
    "test_sort(quick_sort, samples=100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}